package leetcode_1901_2000;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;

public class LeeCode_1926 {
    public static void main(String[] args) {
        System.out.println(nearestExit(new char[][]{{'+', '+', '+'}, {'.', '.', '.'}, {'+', '+', '+'}}, new int[]{1, 0}));
        System.out.println(nearestExit(new char[][]{{'+','.','+','+','+','+','+'},{'+','.','+','.','.','.','+'},
                {'+','.','+','.','+','.','+'},{'+','.','.','.','.','.','+'},{'+','+','+','+','.','+','.'}}
, new int[]{0,1}));
    }

    private static int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length, n = maze[0].length;
        Deque<int[]> queue = new ArrayDeque<>();
        queue.add(entrance);
        int step = 0;
        int[][] vis = new int[m][n];
        vis[entrance[0]][entrance[1]] = 1;
        int[] cha = new int[]{1, -1};
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] pop = queue.pop();
                int x = pop[0], y = pop[1];
                for (int j = 0; j < 2; j++) {
                    int nx = x + cha[j];
                    if (nx < 0 || nx >= m || y < 0 || y >= n) {
                        continue;
                    }
                    if (maze[nx][y] == '+' || vis[nx][y] == 1) {
                        continue;
                    }
                    if (nx == 0 || nx == m - 1 || y == 0 || y == n - 1)
                        return step + 1;
                    queue.offer(new int[]{nx, y});
                    vis[nx][y] = 1;
                }
                for (int j = 0; j < 2; j++) {
                    int ny = y + cha[j];
                    if (x < 0 || x >= m || ny < 0 || ny >= n) {
                        continue;
                    }
                    if (maze[x][ny] == '+' || vis[x][ny] == 1) {
                        continue;
                    }
                    if (x == 0 || x == m - 1 || ny == 0 || ny == n - 1)
                        return step + 1;
                    queue.offer(new int[]{x, ny});
                    vis[x][ny] = 1;
                }
            }
            step++;

        }
        return -1;
    }
}
